{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #First Bad Version"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-search #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #二分查找 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: firstBadVersion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第一个错误的版本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。</p>\n",
    "\n",
    "<p>假设你有 <code>n</code> 个版本 <code>[1, 2, ..., n]</code>，你想找出导致之后所有版本出错的第一个错误的版本。</p>\n",
    "\n",
    "<p>你可以通过调用 <code>bool isBadVersion(version)</code> 接口来判断版本号 <code>version</code> 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。</p>\n",
    " \n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, bad = 4\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "<code>调用 isBadVersion(3) -> false \n",
    "调用 isBadVersion(5) -> true \n",
    "调用 isBadVersion(4) -> true</code>\n",
    "<code>所以，4 是第一个错误的版本。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, bad = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= bad <= n <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [first-bad-version](https://leetcode.cn/problems/first-bad-version/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [first-bad-version](https://leetcode.cn/problems/first-bad-version/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n4', '1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left,right=0,n-1\n",
    "        while left<=right:\n",
    "            middle=left+(right-left)//2\n",
    "            if isBadVersion(middle):\n",
    "                right=middle-1                \n",
    "            else:\n",
    "                left=middle+1\n",
    "        return left\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        return __bad__\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i,j=1,n\n",
    "        while i<=j:\n",
    "            m = (i+j)//2\n",
    "            if isBadVersion(m):\n",
    "                j = m-1\n",
    "            else:\n",
    "                i = m+1\n",
    "        return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l = 1\n",
    "        r = n\n",
    "        while (l <= r):\n",
    "            mid = (l + r) // 2\n",
    "            if isBadVersion(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        a, b = 1, n\n",
    "        while a < b:\n",
    "            c = (a+b)//2\n",
    "            if isBadVersion(c):\n",
    "                b = c\n",
    "            else:\n",
    "                a = c + 1\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        ans = 1\n",
    "        while left<=right:\n",
    "            mid = (right+left)//2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid-1\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        # 找左边界\n",
    "        left, right = 0,n\n",
    "        while left<right:\n",
    "            mid = left+(right-left)//2\n",
    "            detact = isBadVersion(mid)\n",
    "            if detact:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left,right = 1,n\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        #左闭右闭,找到最后一个正确的，然后加1\n",
    "        if n==1:return 1 \n",
    "        left,right=1,n\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if isBadVersion(mid) is True:\n",
    "                if isBadVersion(mid-1) is False:\n",
    "                    return mid\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        # 二分法查找第一个测试判断为true的位置，也就是交界处,每次折半判定条件中，如果是true,往左走(right-1)，否则往右走(left+1),最后退出返回right+1\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid) == True:\n",
    "                # 此时mid版本已是坏的,往左走，继续回退\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                # 此时mid版本是正常的，往右走，看后面的版本\n",
    "                left = mid + 1\n",
    "        # 最后停留在False/True交界处\n",
    "        return left\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        # 右边区域的左顶点 >=\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid + 1):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l,r=0,n\n",
    "        while l<=r:\n",
    "            m=l+(r-l)//2\n",
    "            if isBadVersion(m):\n",
    "                r=m-1\n",
    "            else:\n",
    "                l=m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l,r=1,n\n",
    "        ans=1\n",
    "\n",
    "        while l<=r:\n",
    "            m = (l + r) // 2\n",
    "\n",
    "            if isBadVersion(m):\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid) == True:\n",
    "                if isBadVersion(mid - 1) == False:\n",
    "                    return mid\n",
    "                else:\n",
    "                    right = mid -1 \n",
    "            elif isBadVersion(mid) == False:\n",
    "                if isBadVersion(mid + 1) == True:\n",
    "                    return mid + 1\n",
    "                else:\n",
    "                    left = mid\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left,right=1,n\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if isBadVersion(mid)==False:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return left\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        begin = 1\n",
    "        end = n+1\n",
    "        while begin < end:\n",
    "            mid = (end + begin) // 2\n",
    "            if not isBadVersion(mid):\n",
    "                begin = mid + 1\n",
    "            else:\n",
    "                end = mid\n",
    "        return end\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            if not isBadVersion(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i = 0\n",
    "        j = n\n",
    "        while i < j:\n",
    "            mid = (i + j) // 2\n",
    "            if isBadVersion(mid) == False:\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid\n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right=0, n\n",
    "        while left<right:\n",
    "            m=left+(right-left)//2\n",
    "            if not isBadVersion(m):\n",
    "                left=m+1\n",
    "            else:\n",
    "                right=m\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if isBadVersion(mid):right = mid-1\n",
    "            else:left=mid+1\n",
    "        \n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        t=n//2\n",
    "        l=0\n",
    "        while True:\n",
    "            if isBadVersion(t):\n",
    "                t=(t+l)//2\n",
    "            else:\n",
    "                if isBadVersion(t+1):\n",
    "                    return t+1\n",
    "                else:\n",
    "                    l=t\n",
    "                    t=(t+n)//2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while (left<right):\n",
    "            mid = left + (right - left)//2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l=0\n",
    "        r=n+1\n",
    "        m=(l+r)//2\n",
    "        while l+1!=r:\n",
    "            if not isBadVersion(m):\n",
    "                l=m\n",
    "                m=(l+r)//2\n",
    "            else:\n",
    "                r=m\n",
    "                m=(l+r)//2\n",
    "        return r\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i, j = 1, n\n",
    "        while i <= j:\n",
    "            mid = (i+j)//2\n",
    "            if isBadVersion(mid): j = mid-1\n",
    "            else: i = mid+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 0\n",
    "        right = n\n",
    "        while right > left:\n",
    "            mid = (left+right) // 2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l = 1\n",
    "        r = n\n",
    "        mid = (l+r)//2\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if isBadVersion(mid):\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i, j = 1, n\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if isBadVersion(m): j = m - 1\n",
    "            else: i = m + 1\n",
    "        return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l,r=0,n-1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if isBadVersion(mid):\n",
    "                r = mid -1\n",
    "            else:\n",
    "                l =mid +1\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        if isBadVersion(left):\n",
    "            return 1\n",
    "        right = n\n",
    "        while left<right-1:\n",
    "            mid = ceil((right-left)/2)+left\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        i, j = 1, n\n",
    "        while i < j:\n",
    "            mid = i + ((j - i) >> 1)\n",
    "            if not isBadVersion(mid): i = mid + 1\n",
    "            else: j = mid\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        return __bad__\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left <= right-1:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid):     # 错误的版本\n",
    "                if not isBadVersion(mid-1):\n",
    "                    return mid\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l = 0\n",
    "        r = n\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if isBadVersion(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 二分法\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i = 0\n",
    "        while i <= n:\n",
    "            m = (i+n) // 2\n",
    "            if isBadVersion(m):\n",
    "                if not isBadVersion(m-1):\n",
    "                    return m\n",
    "                else:\n",
    "                    n = m - 1\n",
    "            else:\n",
    "                i = m + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if isBadVersion(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "# 1 2 3 4 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l = 0\n",
    "        r = n\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if isBadVersion(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        # tttttffffffff\n",
    "        l,r = 0, n\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if isBadVersion(mid):r=mid\n",
    "            else: l=mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i, j = 1, n\n",
    "        while i <= j:\n",
    "            # 向下取整除法计算中点 m \n",
    "            m = (i + j) // 2\n",
    "            # 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]\n",
    "            if isBadVersion(m): j = m - 1\n",
    "            # 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]\n",
    "            else: i = m + 1\n",
    "        # i 指向首个错误版本，j 指向最后一个正确版本\n",
    "        return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            flag = isBadVersion(mid)\n",
    "            if flag:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l = 0\n",
    "        r = n + 1\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            check = isBadVersion(mid)\n",
    "            if check:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left<= right:\n",
    "            mid = (left+right) //2\n",
    "            if isBadVersion(mid) is True:\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if isBadVersion(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left<=right:\n",
    "            mid = left + (right-left)//2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if right>n:\n",
    "            return n\n",
    "        return max(left,right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if isBadVersion(mid):\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        low = 0\n",
    "        high = n\n",
    "        while low <= high:\n",
    "            mid = (high+low)//2\n",
    "            if isBadVersion(mid):\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        start = 1\n",
    "        end = n\n",
    "        while start< end:\n",
    "            mid = start + (end - start)//2\n",
    "            if isBadVersion(mid) :\n",
    "                end = mid\n",
    "            else :\n",
    "                start = mid + 1\n",
    "        return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l, r = 0, n-1\n",
    "        m = 0\n",
    "        if n == 1: return 1\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if isBadVersion(m):\n",
    "                r = m-1\n",
    "            else: l = m+1\n",
    "        return m+1 if not isBadVersion(m) else m\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        start = 1\n",
    "        stop = n\n",
    "        while(stop - start>1):\n",
    "            a = (start + stop)  //2\n",
    "            if isBadVersion(a):\n",
    "                stop = a\n",
    "            else:\n",
    "                start = a\n",
    "        if isBadVersion(start):\n",
    "            return start\n",
    "        else:\n",
    "            return stop\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left if isBadVersion(left) else \\\n",
    "            right if isBadVersion(right) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i=1\n",
    "        j=n\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if isBadVersion(m):\n",
    "                j=m-1\n",
    "            else:\n",
    "                i=m+1\n",
    "        return i\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "    \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        # 二分查找, 这题跟猜数字几乎一样\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if not isBadVersion(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        ans = 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if isBadVersion(mid) == True:\n",
    "                right = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\r\n",
    "# def isBadVersion(version: int) -> bool:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def firstBadVersion(self, n: int) -> int:\r\n",
    "        left, right = 1, n\r\n",
    "        while left <= right:\r\n",
    "            mid = left + (right - left) // 2\r\n",
    "            if not isBadVersion(mid):\r\n",
    "                left = mid + 1\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "        return left\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if not isBadVersion(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        low = 1\n",
    "        high = n\n",
    "        while high>low:\n",
    "            mid=(low+high)//2\n",
    "            if isBadVersion(mid):\n",
    "                high=mid\n",
    "            if not isBadVersion(mid):\n",
    "                low=mid +1\n",
    "        return low        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n -1\n",
    "        while left<= right:\n",
    "            mid = (left+right) //2\n",
    "            if isBadVersion(mid) is True:\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        start = 1\n",
    "        end = n\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if not isBadVersion(mid):\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid\n",
    "        return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i = 1\n",
    "        j = n\n",
    "        f = -1\n",
    "        while i<=j:\n",
    "            m = (j - i) //2 + i\n",
    "            if isBadVersion(m):\n",
    "                j = m-1\n",
    "                f = m\n",
    "            else:\n",
    "                i = m+1\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid  + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if isBadVersion(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            left = 1\n",
    "            right = n\n",
    "            while left <= right:\n",
    "                middle = (left +right) // 2\n",
    "                if isBadVersion(middle) is False:\n",
    "                    left = middle +1\n",
    "                elif isBadVersion(middle) is True:\n",
    "                    right = middle -1\n",
    "                if isBadVersion((left +right) // 2) is False and isBadVersion(((left +right) // 2)+1) is True:\n",
    "                    return ((left +right) // 2)+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l,r=0,n+1\n",
    "        while l<r-1:\n",
    "            mid=(l+r)>>1\n",
    "            if isBadVersion(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\r\n",
    "# def isBadVersion(version: int) -> bool:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def firstBadVersion(self, n: int) -> int:\r\n",
    "        left = 1\r\n",
    "        right = n\r\n",
    "        while left < right:\r\n",
    "            binary = left + (right - left) // 2\r\n",
    "            if isBadVersion(binary):\r\n",
    "                right = binary\r\n",
    "            else:\r\n",
    "                left = binary + 1\r\n",
    "        return left\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        left = 0\n",
    "        right = n\n",
    "        while right > left:\n",
    "            mid = (left+right) // 2\n",
    "            if isBadVersion(mid) == True:\n",
    "                if isBadVersion(mid) == isBadVersion(mid-1):\n",
    "                    right = mid\n",
    "                else:\n",
    "                    return mid\n",
    "            elif isBadVersion(mid) == False:\n",
    "                if isBadVersion(mid) == isBadVersion(mid+1):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    return mid+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        i=1\n",
    "        j=n\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if isBadVersion(m):\n",
    "                j=m-1\n",
    "            else:\n",
    "                i=m+1\n",
    "\n",
    "        return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return self.find(1,n)\n",
    "        \n",
    "    def find(self,n1,n2):\n",
    "        if n1 == n2:\n",
    "            return n1\n",
    "        mid = (n1+n2)//2\n",
    "        if isBadVersion(mid) == True:\n",
    "            return self.find(n1,mid)\n",
    "        else:\n",
    "            return self.find(mid + 1,n2)\n",
    "\n",
    "\n",
    "            \n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        first  = 1\n",
    "        last = n\n",
    "        while first <= last:\n",
    "            mid = (first + last)//2\n",
    "            if isBadVersion(mid) and not isBadVersion(mid-1) :\n",
    "                return mid\n",
    "            elif isBadVersion(mid) and isBadVersion(mid-1) :\n",
    "                last = mid-1\n",
    "\n",
    "            elif not isBadVersion(mid):\n",
    "                first = mid+1\n",
    "        return 1\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int:\n",
    "        l,r,res=0,n,-1\n",
    "        if n==1:\n",
    "            return 1\n",
    "        while(l<=r):\n",
    "            mid=(l+r)//2\n",
    "            if(isBadVersion(mid)):\n",
    "                res=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The isBadVersion API is already defined for you.\n",
    "# def isBadVersion(version: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def firstBadVersion(self, n: int) -> int: ## 二分法查找\n",
    "        i, j = 1, n\n",
    "        while i <= j:\n",
    "            # 向下取整除法计算中点 m \n",
    "            m = (i + j) // 2\n",
    "            # 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]\n",
    "            if isBadVersion(m): j = m - 1\n",
    "            # 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]\n",
    "            else: i = m + 1\n",
    "        # i 指向首个错误版本，j 指向最后一个正确版本\n",
    "        return i\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
